#!/usr/bin/env python
#-*- coding:utf-8 -*-
# turingmachine.py
# Maquina de Turing

# Copyright (c) 2007 Marcelo Lira dos Santos
#
# Author: Marcelo Lira dos Santos <setanta@gmail.com>
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation; either version 2 of the
# License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
# USA

class TuringMachine:

    (
    LEFT,
    RIGHT
    ) = range(2)

    (
    ACCEPT,
    REJECT,
    NONE
    ) = range(3)

    def __init__(self, states=None, input_alphabet=None, tape_alphabet=None,
            transition_function=None, start_state=None, accept_state=None,
            reject_state=None):
        self.states = states
        self.input_alphabet = input_alphabet
        self.tape_alphabet = tape_alphabet
        self.transition_function = transition_function
        self.start_state = start_state
        self.accept_state = accept_state
        self.reject_state = reject_state
        self.string = None

        self.current_state = start_state
        self.tape = None
        self.head = 0
        self.steps = 0

        self.debug = False


    def set_states(self, states):
        states.sort()
        self.states = states

    def set_input_alphabet(self, input_alphabet):
        self.input_alphabet = input_alphabet

    def set_tape_alphabet(self, tape_alphabet):
        self.tape_alphabet = tape_alphabet

    def set_start_state(self, start_state):
        self.start_state = start_state

    def set_accept_state(self, accept_state):
        self.accept_state = accept_state

    def set_reject_state(self, reject_state):
        self.reject_state = reject_state

    def set_transition_function(self, transition_function):
        self.transition_function = transition_function

    def set_string(self, string):
        if not self.validate_string(string):
            #FIXME: jogue uma excecao adequada
            print 'string invalida'
            return

        self.string = string

    def set_head(self, head=0):
        self.head = head

    def get_states(self):
        return self.states

    def get_current_state(self):
        return self.current_state

    def get_input_alphabet(self):
        return self.input_alphabet

    def get_tape_alphabet(self):
        return self.tape_alphabet

    def get_start_state(self):
        return self.start_state

    def get_accept_state(self):
        return self.accept_state

    def get_reject_state(self):
        return self.reject_state

    def get_transition_function(self):
        return self.transition_function

    def get_string(self):
        return self.string

    def get_head(self):
        return self.head

    def get_tape(self):
        return self.tape

    def validate_machine(self):
        '''Retorna True se os atributos da maquina estiverem corretos.'''

        if not self.states:
            return False

        if self.start_state not in self.states or\
                self.accept_state not in self.states or\
                self.reject_state not in self.states:
            return False

        if not set(self.transition_function).issubset(self.states):
            return False

        #FIXME: verificar os valores dentro de self.trans_func...

        return True


    def validate_string(self, string):
        return set(string).issubset(self.input_alphabet)


    def reset(self):
        self.current_state = self.start_state
        # FIXME: a fita eh infinita a direita.
        self.tape = list(self.string)
        self.head = 0
        self.steps = 0


    def step_back(self):
        if self.steps < 1:
            return

        steps = self.steps - 1
        self.reset()
        self.compute(steps)


    def compute(self, steps=-1):
        while steps != 0:
            steps -= 1
            accept = self.compute_step()
            if accept == TuringMachine.ACCEPT:
                return True
            elif accept == TuringMachine.REJECT:
                return False


    def compute_step(self):
        self.steps += 1

        if self.current_state == self.accept_state:
            return TuringMachine.ACCEPT

        read_symbol = self.tape[self.head]
        current_state_trans = self.transition_function[self.current_state]

        if not current_state_trans.has_key(read_symbol):
            return TuringMachine.REJECT
        else:
            next_state, write_symbol, move = \
                    current_state_trans[read_symbol]

        if self.debug:
            print '(state:%s,head:%d,read:%s): ->%s w:%s, m:%d -- %s' % \
                   (self.current_state, self.head, read_symbol, next_state, \
                   write_symbol, move, ''.join(self.tape))

        if write_symbol != None:
            self.tape[self.head] = write_symbol

        self.current_state = next_state

        if self.current_state == self.reject_state:
            return TuringMachine.REJECT
        elif self.current_state == self.accept_state:
            return TuringMachine.ACCEPT

        if move == TuringMachine.LEFT:
            self.head -= 1
            if self.head < 0:
                    self.head = 0
        else:
            self.head += 1
            if self.head == len(self.tape):
                self.tape.append(' ')

        return TuringMachine.NONE


    def generate_graph(self):
        dot_graph = 'digraph turing_machine {\n'
        dot_graph += '    edge [fontname=helvetica,fontsize=9]\n'
        dot_graph += '    node [fontname=helvetica,fontsize=9,shape=doublecircle];'
        dot_graph += self.accept_state + '\n'
        dot_graph += '    node [shape=circle,size=8]\n'
        dot_graph += '    start [shape=point]\n'
        dot_graph += '    start -> %s\n' % self.start_state

        for state in self.states:
            if not self.transition_function.has_key(state):
                continue

            values = self.transition_function[state].keys()
            values.sort()

            tmp_values = {}

            for value in values:
                next_state, write, movement = \
                        self.transition_function[state][value]

                right_side = ''
                if write:
                    right_side += write + ','

                if movement == TuringMachine.RIGHT:
                    right_side += 'R'
                else:
                    right_side += 'L'

                if value == ' ':
                    read_value = '_'
                else:
                    read_value = value

                if tmp_values.has_key((next_state, right_side)):
                    tmp_values[(next_state, right_side)].append(read_value)
                else:
                    tmp_values[(next_state, right_side)] = [read_value]

            for value in tmp_values.keys():
                left_side = ','.join(tmp_values[value])
                next_state, right_side = value
                dot_graph += '    %s -> %s [label=\"%s->%s\"]\n' % \
                        (state, next_state, left_side, right_side)

        dot_graph += '}\n'

        return dot_graph


def test():
    tm = TuringMachine()
    tm.debug = True
    # A maquina de turing deste teste.
    states = ['q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'q7', 'q8', 'qa', 'qr']
    tm.set_states(states)
    tm.set_start_state('q1')
    tm.set_accept_state('qa')
    tm.set_reject_state('qr')
    tm.set_input_alphabet(['0', '1', '#'])
    tm.set_tape_alphabet(['x', ' '])

    # Funcao de transicao
    trans_func = {
        'q1': {'0': ('q2', 'x', TuringMachine.RIGHT),
               '1': ('q3', 'x', TuringMachine.RIGHT),
               '#': ('q8', None, TuringMachine.RIGHT)},
        'q2': {'0': ('q2', None, TuringMachine.RIGHT),
               '1': ('q2', None, TuringMachine.RIGHT),
               '#': ('q4', None, TuringMachine.RIGHT)},
        'q3': {'0': ('q3', None, TuringMachine.RIGHT),
               '1': ('q3', None, TuringMachine.RIGHT),
               '#': ('q5', None, TuringMachine.RIGHT)},
        'q4': {'0': ('q6', 'x', TuringMachine.LEFT),
               'x': ('q4', None, TuringMachine.RIGHT)},
        'q5': {'1': ('q6', 'x', TuringMachine.LEFT),
               'x': ('q5', None, TuringMachine.RIGHT)},
        'q6': {'0': ('q6', None, TuringMachine.LEFT),
               '1': ('q6', None, TuringMachine.LEFT),
               'x': ('q6', None, TuringMachine.LEFT),
               '#': ('q7', None, TuringMachine.LEFT)},
        'q7': {'0': ('q7', None, TuringMachine.LEFT),
               '1': ('q7', None, TuringMachine.LEFT),
               'x': ('q1', None, TuringMachine.RIGHT)},
        'q8': {' ': ('qa', None, TuringMachine.RIGHT),
               'x': ('q8', None, TuringMachine.RIGHT)}
    }

    tm.set_transition_function(trans_func)

    if not tm.validate_machine():
        #FIXME: jogue uma excecao adequada
        print 'maquina invalida'
        return

    #string = '101111100011#101111100011'

    string = '101111100011#000000000000'
    tm.set_string(string)
    print '\nprocessando: ' + string
    tm.reset()
    accept = tm.compute()
    print accept

    '''
    string = '1011#1011'
    tm.set_string(string)
    print '\nprocessando: ' + string
    accept = TuringMachine.NONE
    i = 0
    while accept != TuringMachine.ACCEPT:
        i += 1
        print '\nproc ' + str(i)
        tm.reset()
        for j in range(i):
            accept = tm.compute_step()
    print '  aceita: ', accept

    print '\n-----------------------------------------\n'
    '''
    grafo = tm.generate_graph()

    print grafo

    f = open('turingmachine.dot', 'w')
    f.write(grafo)
    f.close()


if __name__ == '__main__':
    test()

